Thực đơn
Bài toán vận tải Bài toánGiả sử có m kho hàng A 1 , . . , A m {\displaystyle A_{1},..,A_{m}} cùng chứa một loại hàng hóa, kho A i {\displaystyle A_{i}} chứa a i {\displaystyle a_{i}} tấn hàng. Cần vận chuyển số hàng trên đến n cửa hàng B 1 , . . . , B n {\displaystyle B_{1},...,B_{n}} , cửa hàng B i {\displaystyle B_{i}} cần số hàng b i {\displaystyle b_{i}} . Cước phí vận chuyển một tấn hàng từ kho A i {\displaystyle A_{i}} đến cửa hàng B j {\displaystyle B_{j}} là c i j {\displaystyle c_{ij}} . Hãy lập phương án vận chuyển sao cho tổng chi phí vận chuyển là nhỏ nhất.
Các kho hàng được gọi là các điểm phát, các cửa hàng được gọi là các điểm thu.Ví dụ: Có 3 điểm phát và 4 điểm thu, số hàng ở các điểm phát, nhu cầu ở các điểm thu, cước phí vận chuyển cho trong bảng sau:
Bảng dữ liệu và phương án X[i, j] của bài toán vận tảiBảng trên đây được gọi là bảng vận tải.
Mỗi phương án vận chuyển là một ma trận X = [ x i j ] {\displaystyle \left[x_{ij}\right]} , trong đó x i j {\displaystyle x_{ij}} là số hàng hóa chuyển từ Ai đến Bj. ( x i j ≥ 0 {\displaystyle x_{ij}\geq 0} )
Chi phí vận chuyển của phương án X là:
G ( X ) = ∑ i = 1 m ∑ j = 1 n c i j . x i j {\displaystyle G(X)=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}.x_{ij}}Để một phương án thực sự là chấp nhận được cho bài toán vận tải, các giá trị x i , j {\displaystyle x_{i,j}} phải thỏa mãn các ràng buộc đối với các điểm phát (ràng buộc dòng) là
∑ j = 1 n x i j = a i {\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i}\,} với mọi i=1,..,m.và các ràng buộc với các điểm thu (ràng buộc cột)
∑ i = 1 m x i j = b j {\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j}\,} với mọi j=1,..,n.Như vậy bài toán vận tải là bài toán QHTT dạng chính tắc với m × {\displaystyle \times } n biến, hàm mục tiêu G(X) cần cực tiểu và m+n ràng buộc.
Thực đơn
Bài toán vận tải Bài toánLiên quan
Bài Tiến lên Bài toán người bán hàng Bài toán 3 vật thể Bài hát hay nhất Bài hát hay nhất (mùa 1) Bài hát hay nhất (mùa 3) Bài hát hay nhất (mùa 2) Bài ngoại và phân biệt chủng tộc liên quan đến đại dịch COVID-19 Bài tấn Bài hát của cá voiTài liệu tham khảo
WikiPedia: Bài toán vận tải